package day0;

import java.util.*;

public class code4 {

    public int[][] merge(int[][] intervals) {

        ArrayList<int[]> list = new ArrayList<>();
        Arrays.sort(intervals,(a,b)->a[0]==b[0]?a[1]-b[1]:a[0]-b[0]);

        int[] pre = intervals[0];
        for (int i = 1; i < intervals.length; i++) {
            int[] las = intervals[i];
            int left = pre[0];
            int right = pre[1];
            if(las[0]>=left&&las[0]<=right){
                right = Math.max(las[1],right);
                pre[1] = right;
            }else {
                list.add(new int[]{left,right});
            }
        }

        int[][] arr = new int[list.size()][2];
        for (int i = 0; i < list.size(); i++) {
            arr[i][0] = list.get(i)[0];
            arr[i][1] = list.get(1)[1];
        }

        return arr;
    }

    public void rotate(int[] nums, int k) {

        k = k%nums.length;
        fun(0,k-1,nums);
        fun(k,nums.length-1,nums);
        fun(0,nums.length-1,nums);

    }

    public void fun(int lt,int rt,int[] nums){
        while (lt<rt){
            int num = nums[lt];
            nums[lt] =  nums[rt];
            nums[rt] = num;
            lt += 1;
            rt -= 1;
        }
    }

    public int firstMissingPositive(int[] nums) {
        
        int[] arr = new int[nums.length+1];

        for (int i = 0; i < nums.length; i++) {
            if(nums[i]>0&&nums[i]<=nums.length){
                arr[nums[i]] = 1;
            }
        }

        for (int i = 0; i < arr.length; i++) {
            if(arr[i]<0){
                return i+1;
            }
        }
        return nums.length+1;

    }


    public boolean searchMatrix(int[][] matrix, int target) {

        int m = 0;
        int n = matrix[0].length;

        while (fun1(m,n,matrix)){
            if(matrix[m][n]==target) return true;

            if(matrix[m][n]>target){
                m += 1;
            }else {
                n -= 1;
            }

        }
        return false;

    }

    private boolean fun1(int m, int n, int[][] matrix) {
        if(m<0 || m>matrix.length-1) return false;
        if(n<0 || n>matrix[0].length-1) return false;
        return true;
    }


    public List<Integer> spiralOrder(int[][] matrix) {

        List<Integer> list = new ArrayList<>();
        int[][] arr = new int[][]{{0,1},{1,0},{0,-1},{-1,0}};

        int step = matrix.length*matrix[0].length;

        int m = 0;
        int n = 0;
        int index = 0;
        matrix[m][n]=200;
        list.add(arr[m][n]);
        for (int i = 1; i < step; i++) {
            while (!def(m,n,index,arr,matrix)){
                index = (index+1)%4;
            }
            m += arr[index][0];
            n += arr[index][1];
            list.add(matrix[m][n]);
            matrix[m][n]=200;
        }

        return list;




    }

    private boolean def(int m, int n, int index, int[][] arr,int[][] matrix) {
        m += arr[index][0];
        n += arr[index][1];
        if(m<0 || m>=matrix.length) return false;
        if(n<0 || n>=matrix[0].length) return false;
        return matrix[m][n] != 200;
    }

    public static void main(String[] args) {

        //栈
        LinkedList<Integer> stack = new LinkedList<>();
        stack.push(1);
        stack.push(2);
        System.out.println(stack.peek());
        stack.pop();
        System.out.println(stack.peek());



        //队列
        Queue<Integer> queue =new ArrayDeque<>();
        queue.offer(1);
        queue.offer(2);
        System.out.println(queue.peek());
        queue.poll();
        System.out.println(queue.peek());






    }


}
